package main

import (
	"fmt"
)

/**
执行用时：12 ms, 在所有 Go 提交中击败了77.14%的用户
内存消耗：6.6 MB, 在所有 Go 提交中击败了42.34%的用户
 */
func findSubstring(s string, words []string) []int {

	res := []int{}
	if len(words) == 0 { return res }

	n, m, w := len(s), len(words), len(words[0])

	tot := make(map[string]int)
	for _, word := range words { tot[word]++ }

	for i := 0; i < w; i++ {
		wd := map[string]int{}
		cnt := 0
		for j := i; j + w - 1 < n; j += w {
			if j >= i + m * w {  // 滑出一个单词
				word := s[j - m * w : j - m * w + w]
				wd[word]--
				if wd[word] < tot[word] { cnt-- }
			}
			// 滑入一个单词
			word := s[j : j + w]
			wd[word]++
			if wd[word] <= tot[word] { cnt++ }
			if cnt == m { res = append(res, j - (m - 1) * w) }
		}
	}
	return res
}

func main() {

	s := "barfoothefoobarman"
	words := []string{"foo","bar"}
	fmt.Println(findSubstring(s, words))
}
